package Top200;

/**
 * @author zhangmin
 * @create 2022-02-25 10:05
 * 先对第一列进行二分查找，然后再在行中二分查找
 */
public class searchMatrix74 {
    public boolean searchMatrix(int[][] matrix, int target) {
        int m=matrix.length,n=matrix[0].length;
        if (target<matrix[0][0]||target>matrix[m-1][n-1]) return false;
        //按第一列进行二分查找
        int top=0,down=m-1;
        while (top<=down){
            int mid=top+(down-top)/2;
            if (matrix[mid][0]==target){
                return true;
            }else if (matrix[mid][0]<target){
                top=mid+1;
            }else {
                down=mid-1;
            }
        }
        int row=top-1;
        int left=0,right=n-1;
        while (left<=right){
            int mid=left+(right-left)/2;
            if (matrix[row][mid]==target) return true;
            else if (matrix[row][mid]<target){
                left=mid+1;
            }else {
                right=mid-1;
            }
        }
        return matrix[row][left]==target;
    }
}
